/*
 * @Author: szx
 * @Date: 2022-01-30 14:07:36
 * @LastEditTime: 2022-04-12 14:09:52
 * @Description:
 * @FilePath: \leetcode\1-99\84\84.js
 */
/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
    // 难就难在本题要记录记录每个柱子 左边第一个小于该柱子的下标，而不是左边第一个小于该柱子的高度。
    let res = 0;
    const n = heights.length;
    const minLeftIndex = new Array(n);
    const minRightIndex = new Array(n);
    minLeftIndex[0] = -1; // 注意这里初始化，防止下面while死循环

    for (let i = 1; i < n; i++) {
        let t = i - 1;
        while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
        minLeftIndex[i] = t;
    }
    minRightIndex[n - 1] = n; // 注意这里初始化，防止下面while死循环
    for (let i = n - 2; i >= 0; i--) {
        let t = i + 1;
        while (t < n && heights[t] >= heights[i]) t = minRightIndex[t];
        minRightIndex[i] = t;
    }
    for (let i = 0; i < n; i++) {
        res = Math.max(res, heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1));
    }
    return res;
};

// 单调栈
var largestRectangleArea = function (heights) {
    // 单调递增的
    let res = 0;
    const st = [0];
    heights = [0,...heights,0]; // 数组头部加入元素0 数组尾部加入元素0
    for (let i = 1; i < heights.length; i++) {
        while (st.length && heights[i] < heights[st[st.length - 1]]) {
            const mid = st.pop();
            res = Math.max(res, (i - st[st.length - 1] - 1) * heights[mid]);
        }
        st.push(i);
    }
    return res;
};
